package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_47_全排列II {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_47_全排列II().permuteUnique(new int[]{1,1,2}));
        System.out.println(new 力扣_47_全排列II().permuteUnique(new int[]{1,2,3}));
    }

    /**
    题目：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

     示例 1：
     输入：nums = [1,1,2]
     输出：
     [[1,1,2],
     [1,2,1],
     [2,1,1]]

     示例 2：
     输入：nums = [1,2,3]
     输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
      
     提示：
     1 <= nums.length <= 8
     -10 <= nums[i] <= 10

    分析：【BR 💞💞💞💞】
       1.回溯，同样用数组记录已经使用过的数字？
            --执行用时：2 ms, 在所有 Java 提交中击败了43.85%的用户
        难点：重复出现的问题.解：排序，然后通过相邻来确认
             这里如果前面的是未被使用，隔空说明自己是起点。要走就跟大哥一起走，不然就摆烂
        优化：队列就是比Stack快啊--晕
            --执行用时：1 ms, 在所有 Java 提交中击败了99.81%的用户

    边界值 & 注意点：
       1.
     **/
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        //2.使用 boolean[]  存储true false 表示使用过没
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        boolean[] used = new boolean[nums.length];
        recursive(nums,used, stack, res);
        return res;
    }

    /**
     *  回溯 1,2,3
     * @param  nums  目标数组
     * @param  used 记录使用过没
     * @param  stack 前面已经加入的节点
     * @param  res  结果集合
     **/
    private void recursive(int[] nums, boolean[] used, Deque<Integer> stack, List<List<Integer>> res) {
         if(stack.size()==nums.length){
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(!used[i]){
                if(i > 0 && nums[i] == nums[i - 1] &&!used[i-1])//这里如果前面的是未被使用，隔空说明自己是起点。要走就跟大哥一起走，不然就摆烂
                    continue;                   
                stack.add(nums[i]);
                used[i] =true;
                recursive(nums, used, stack, res);
                used[i] =false;
                stack.pollLast();
            }
        }
    }
}
